package chixing.day15.work;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// 双向链表节点
class Node {
    int key;
    int value;
    Node prev;
    Node next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

// LRU Cache实现
class LRUCache {
    private int capacity;
    private Map<Integer, Node> cache;
    private Node head;  // 虚拟头节点
    private Node tail;  // 虚拟尾节点

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();

        // 初始化虚拟节点
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    // 将节点添加到头部（最近使用）
    private void addNode(Node node) {
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    // 移除指定节点
    private void removeNode(Node node) {
        Node prevNode = node.prev;
        Node nextNode = node.next;

        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    // 将节点移到头部（标记为最近使用）
    private void moveToHead(Node node) {
        removeNode(node);
        addNode(node);
    }

    // 移除尾部节点（最少使用）并返回
    private Node popTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }

    // 获取key对应的值
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }

        // 将节点移到头部，表示最近使用
        moveToHead(node);
        return node.value;
    }

    // 插入或更新键值对
    public void put(int key, int value) {
        Node node = cache.get(key);

        if (node == null) {
            // 键不存在，创建新节点
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addNode(newNode);

            // 如果超出容量，删除最少使用的节点
            if (cache.size() > capacity) {
                Node tailNode = popTail();
                cache.remove(tailNode.key);
            }
        } else {
            // 键存在，更新值，但不改变位置（不算被使用）
            node.value = value;
        }
    }

    // 主程序处理输入输出
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取容量
        int capacity = scanner.nextInt();
        scanner.nextLine();  // 消耗换行符

        LRUCache cache = new LRUCache(capacity);

        // 处理每一行操作
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (line.isEmpty()) {
                continue;
            }

            String[] parts = line.split(" ");
            if (parts[0].equals("g")) {  // get操作
                int key = Integer.parseInt(parts[1]);
                System.out.println(cache.get(key));
            } else if (parts[0].equals("p")) {  // put操作
                int key = Integer.parseInt(parts[1]);
                int value = Integer.parseInt(parts[2]);
                cache.put(key, value);
            }
        }

        scanner.close();
    }
}
